/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution {
    public String minWindow(String ss, String tt) {
        char[] t = tt.toCharArray(), s = ss.toCharArray();
        int n = s.length, lenT = t.length, count = 0;//有效字符的数量
        int[] hashT = new int[128], hashS = new int[128];
        StringBuilder ret = new StringBuilder();
        int[] tmp = new int[2];
        tmp[0] = -1; tmp[1] = -1;
        int min = Integer.MAX_VALUE;

        //把t数组放进hash表里
        for(char x : t) {
            hashT[x] += 1;
        }

        for(int left = 0, right = 0; right < n; right++) {
            //进窗口
            hashS[s[right]] += 1;
            //进窗口后维护count
            if(hashS[s[right]] <= hashT[s[right]]) count++;
            //判断
            while(count >= lenT) {
                //更新数据
                if(min > right - left + 1) {
                    min = Math.min(min, right - left + 1);
                    tmp[0] = left; tmp[1] = right;
                }
                //出窗口前，维护有效字符count的个数
                if(hashS[s[left]] <= hashT[s[left]]) count--;
                //出窗口
                hashS[s[left]]--;
                left++;
            }
        }
        if(tmp[0] == -1 && tmp[1] == -1) return "";
        ret.append(ss.substring(tmp[0], tmp[1] + 1));
        return new String(ret);
    }
}